package lc;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。
 *
 * 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
 *
 * 例如，
 *
 * [2,3,4] 的中位数是 3
 *
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 *
 * 设计一个支持以下两种操作的数据结构：
 *
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 *
 */
public class QM1720 {

    public static class MedianFinder {

        // 构造两个堆
        // 左边大根堆，右边小根堆
        // 优先级队列其本质就是一个堆
        private PriorityQueue<Integer> left = new PriorityQueue<>(Comparator.reverseOrder());
        private PriorityQueue<Integer> right = new PriorityQueue<>();

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {
        }

        public void addNum(int num) {
            if (left.peek() == null) {
                left.add(num);
            } else {
                if (num <= left.peek()) {
                    left.add(num);
                } else {
                    right.add(num);
                }
            }
            // 调整两边树大小
            while (left.size() < right.size()) {
                // 控制左边树比右边树大
                final Integer poll = right.poll();
                left.add(poll);
            }
            // 控制右边树最多只能比左边树小1个
            while (left.size() - right.size() > 1) {
                final Integer poll = left.poll();
                right.add(poll);
            }

        }

        public double findMedian() {
            if (left.peek() == null) {
                return 0.0;
            }
            if (left.size() == right.size()) {
                return (double) (left.peek() + right.peek()) / (2.0);
            } else {
                return left.peek();
            }
        }
    }

    public static void main(String[] args) {
        final MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        medianFinder.addNum(3);
        medianFinder.addNum(3);
        medianFinder.addNum(4);
        medianFinder.addNum(5);
        medianFinder.addNum(5);
        System.out.println(medianFinder.findMedian());
    }
}
